package lib

import "math"

func init() {
	Probs = append(Probs, Problem{
		Num:         29,
		Discription: "不用/*实现整除",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
			"位运算":  1,
		},
	})
}

func Divide(dividend int, divisor int) int {
	//确定符号
	sign := 1
	if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
		sign = -1
	}

	if dividend < 0 {
		dividend = -dividend
	}
	if divisor < 0 {
		divisor = -divisor
	}

	res := 0
	//一直将除数*2，直到被除数吃不下，同时记录倍率
	//一旦吃不下，将上一轮被除数剩余的部分取出来当下一轮的被除数，倍率从1继续开始
	for dividend >= divisor {
		tempDivisor := divisor
		multipy := 1
		for dividend >= tempDivisor {
			tempDivisor <<= 1
			multipy <<= 1
		}
		dividend -= tempDivisor >> 1
		res += multipy >> 1
	}

	res *= sign
	if res > math.MaxInt32 {
		return math.MaxInt32
	}
	if res < math.MinInt32 {
		return math.MinInt32
	}

	return res
}
